// N Coins Problem

#include<iostream>
using namespace std;

int c[] = {1,2,5,10,20,50,100,500,1000};
int coin(int i);
void coin();
int p[2000];

int main()
{
	coin();
	int i;
	cout << "\nEnter the amount: ";
	cin >> i;
	cout << "\nMin Number of coins is : " << coin(i) << "\n";
	return 0;
}

void coin()
{
	for(int i=0; i<sizeof(p)/sizeof(int); i++)
	p[i] = -1;
	
	p[0] = 0;
}

int coin(int i)
{
	if(i<0)
	return 1000;
	
	if(p[i]!=-1)
	return p[i];
	
	int min=i;
	for(int k=0; k<sizeof(c)/sizeof(int); k++)
	{
		if(i < c[k])
		break;
		coin(i-c[k]);
		min = min>p[i-c[k]]?p[i-c[k]]:min;
	}
	
	p[i] = 1+min;
	return p[i];
		
}
